#include <utility>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
using namespace std;

enum State{
  EMPTY,
  DELETE,
  EXIST
};

template <class K, class V>
struct HashData{
  pair<K,V> _kv;
  State _state = EMPTY;
};

template <class K>
struct HashKey{
  size_t operator()(const K& k)
  {
    return (size_t)k;
  }
};

template <>
struct HashKey<string>{
  size_t operator()(const string& str)
  {
    size_t ret = 0;
    for(auto ch : str)
    {
      ret *= 131;
      ret += ch;
    }
    return ret;
  }
};

template <class K, class V, class Hash = HashKey<K>>
class HashTable{
  vector<HashData<K,V>> _table;
  size_t _size= 0;

public:
  bool insert(const pair<K,V>& kv){
    if(find(kv.first) != nullptr)
      return false;
    //检查载荷因子，进行扩容
    int tb_size = _table.size();
    if(tb_size == 0 || _size*10/tb_size >= 7)
    {
      int newsize = tb_size==0? 10 : tb_size*2;
      HashTable newHT;
      newHT._table.resize(newsize);
      for(auto &e : _table)
      {
        if(e._state == EXIST)
        newHT.insert(e._kv);
      }
      _table.swap(newHT._table);
    }

    Hash hash;
    int i = 1;
    int hashi = hash(kv.first)%_table.size(); 
    //线性探测
    while(_table[hashi]._state == EXIST)
    {
      hashi += i*i;
      hashi %= _table.size();
      ++i;
    }
    _table[hashi]._kv = kv;
    _table[hashi]._state = EXIST;
    ++_size;
    return true;
  }

  HashData<K,V>* find(const K& k)
  {
    if(_table.size() == 0)
      return nullptr;
    Hash hash;
    int hashi = hash(k)%_table.size(); 
    int start = hashi;
    //线性探测
    //while(_table[hashi]._state != EMPTY)
    //{
    //  if(_table[hashi]._state == EXIST && _table[hashi]._kv.first == k)
    //  {
    //    return &_table[hashi]; 
    //  }
    //  ++hashi;
    //  hashi%=_table.size();
    //  if(hashi == start) //极端情况：表中元素的状态全是DELETE
    //    break;
    //}
    
    int i = 1;
    while(_table[hashi]._state != EMPTY)
    {
      if(_table[hashi]._state == EXIST && _table[hashi]._kv.first == k)
      {
        return &_table[hashi]; 
      }
      hashi += i*i;
      hashi%=_table.size();
      ++i;
      if(hashi == start) //极端情况：表中元素的状态全是DELETE
        break;
    }
    return nullptr;
  }

  bool erase(const K& k)
  {
    HashData<K,V>* ret = find(k);
    if(ret == nullptr)
      return false;
    else
    {
      ret->_state = DELETE;
      --_size;
      return true;
    }
  }

  void printHT(){
    for(int i=0; i<_table.size(); ++i)
    {
      if(_table[i]._state == EXIST)
      {
        //printf("[%d]:%d ", i, _table[i]._kv.first);
        cout << _table[i]._kv.first << ":" << _table[i]._kv.second << endl; 
      }
      //else
      //{
      //  printf("[%d]:* ", i);
      //}
    }
  }
};
